package dev.ece.suit.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

/**
 * 
 * 说明：A*寻路算法
 *
 * AStar.java
 *
 * @author DEVILIVED
 * 
 * 版本信息 v1.0
 * 
 * 2014-3-18
 *
 * 修改历史 
 *
 * Copyright 2014, DEVILIVED Inc.
 */
public class AStar {

	/**
	 * 
	 * 说明：格子坐标
	 *
	 * AStar.java
	 *
	 * @author DEVILIVED
	 * 
	 * 版本信息 v1.0
	 * 
	 * 2014-3-18
	 *
	 * 修改历史 
	 *
	 * Copyright 2014, DEVILIVED Inc.
	 */
	public static class Point {
		
		private int x;
		
		private int y;
		
		private int step = 1;
		
		private int value;
		
		private Point parent;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int getX() {
			return x;
		}

		public int getY() {
			return y;
		}

		public Point getParent() {
			return parent;
		}

		/**
		 * 消耗行动数
		 * @return
		 */
		public int getStep() {
			return step;
		}

		/**
		 * 消耗行动数 ，只在查询行动范围的时候生效，默认为1
		 * @param step
		 */
		public void setStep(int step) {
			this.step = step;
		}

		public int compare(Point point) {
			return this.value > point.value ? 1 : (this.value == point.value ? 0 : -1);
		}
		
		@Override
		public boolean equals(Object obj) {
			if(obj == null) {
				return false;
			}
			if(!(obj instanceof Point)) {
				return false;
			}
			Point point = (Point) obj;
			return x == point.x && y == point.y;
		}
		
	}

	/**
	 * 
	 * 说明：周围可移动点获得接口
	 *
	 * AStar.java
	 *
	 * @author DEVILIVED
	 * 
	 * 版本信息 v1.0
	 * 
	 * 2014-3-18
	 *
	 * 修改历史 
	 *
	 * Copyright 2014, DEVILIVED Inc.
	 */
	public static interface Around {
		/**
		 * 获得point周围可移动的点
		 * @param point
		 * @return
		 */
		public Point[] getLeaf(Point point);
	}

	/**
	 * 获得路径 
	 * @param from 起点
	 * @param to 终点
	 * @param around
	 * @return 路径
	 */
	public static List<Point> findPath(Point from, Point to, Around around) {
		List<Point> result = new ArrayList<Point>();
		Point last = find(from, to, around);
		while(last != null) {
			result.add(0, last);
			last = last.parent;
		}
		return result;
	}
	
	/**
	 * 获得路径 调用to或者返回值的getParent,getParent返回null为没有路径
	 * @param from 起点
	 * @param to 终点
	 * @param around
	 * @return 终点
	 */
	public static Point find(Point from, Point to, Around around) {
		List<Point> open = new ArrayList<Point>();
		List<Point> close = new ArrayList<Point>();
		open.add(from);
		Point point = null;
		Point leaf = null;
		Point temp = null;
		Point[] points = null;
		int value = 0;
		while(!open.isEmpty()) {
			point = open.get(0);
			open.remove(0);
			if(point.equals(to)) {
				to.parent = point.parent;
				return point;
			}
			points = around.getLeaf(point);
			if(points != null) {
				value = point.value + 1;
				for(int i=0; i<points.length; i++) {
					leaf = points[i];
					if(leaf != null) {
						if(open.contains(leaf)) {
							temp = open.get(open.indexOf(leaf));
							if(value < temp.value) {
								temp.value = value;
								temp.parent = point;
							}
						} else if(close.contains(leaf)) {
							continue;
						} else {
							leaf.value = value;
							leaf.parent = point;
							open.add(leaf);
						}
					}
				}
			}
			close.add(point);
			sort(open);
		}
		return to;
	}
	
	/**
	 * 根据行动力查询行动范围
	 * @param from
	 * @param mobility 行动能力
	 * @param around
	 * @return 行动范围列表
	 */
	public static List<Point> find(Point from, int mobility, Around around) {
		List<Point> open = new ArrayList<Point>();
		List<Point> close = new ArrayList<Point>();
		open.add(from);
		Point point = null;
		Point leaf = null;
		Point temp = null;
		Point[] points = null;
		int value = 0;
		while(!open.isEmpty()) {
			point = open.get(0);
			open.remove(0);
			points = around.getLeaf(point);
			if(points != null) {
				for(int i=0; i<points.length; i++) {
					leaf = points[i];
					if(leaf != null) {
						leaf.value = value = point.value + leaf.step;
						if(value <= mobility) {
							if(open.contains(leaf)) {
								temp = open.get(open.indexOf(leaf));
								if(value < temp.value) {
									temp.value = value;
									temp.parent = point;
								}
							} else if(close.contains(leaf)) {
								continue;
							} else {
								leaf.value = value;
								leaf.parent = point;
								open.add(leaf);
							}
						}
					}
				}
			}
			close.add(point);
			sort(open);
		}
		return close;
	}
	
	private static void sort(List<Point> list) {
		Collections.sort(list, new Comparator<Point>() {

			@Override
			public int compare(Point p1, Point p2) {
				return p1.compare(p2);
			}
			
		});
	}
	
	public static void main(String[] args) {
		final int[][] road = new int[][]{
				{0,0,0,0,0,1,1,1,1,1},
				{0,0,0,0,1,0,1,1,1,0},
				{1,1,0,0,0,0,1,0,1,0},
				{1,0,0,0,0,0,0,1,0,0},
				{1,0,1,1,0,1,1,1,0,1},
				{0,0,1,1,0,1,1,0,0,1},
				{0,1,0,0,0,0,1,1,1,0},
				{0,0,1,0,0,0,0,0,0,1},
				{1,1,0,0,1,0,0,0,1,0},
				{0,0,0,0,0,1,1,0,1,1}
		};
		print(road);
		System.out.println("*********************");
		//实现4叉树寻路
		Around around = new Around() {

			@Override
			public Point[] getLeaf(Point point) {
				//返回4叉树,可以是6叉树,8叉树,n叉树
				Point[] ps = new Point[4];
				//北
				int x = point.x;
				int y = point.y - 1;
				ps[0] = this.getPoint(x, y);
				//东
				x = point.x + 1;
				y = point.y;
				ps[1] = this.getPoint(x, y);
				//南
				x = point.x;
				y = point.y + 1;
				ps[2] = this.getPoint(x, y);
				//西
				x = point.x - 1;
				y = point.y;
				ps[3] = this.getPoint(x, y);
				return ps;
			}
			
			private Point getPoint(int x, int y) {
				if(x > -1 && x < 10 && y > -1 && y < 10) {
					if(road[y][x] != 1) {
						return new Point(x, y);
					}
				}
				return null;
			}
		};
		
		//测试
		Point to = find(new Point(1, 1), new Point(2, 8), around);
		//判断是否有路
		System.out.println("行走路径2");
		if(to.getParent() != null) {
			Point temp = to;
			do {
				road[temp.y][temp.x] = 2;
				temp = temp.getParent();
			} while(temp != null);
		}
		//2为行走路径
		print(road);
		System.out.println("*********************");
		java.util.Random random = new java.util.Random();
		for(int i=0; i<10; i++) {
			for(int j=0; j<10; j++) {
				road[i][j] = random.nextInt(2);
			}
		}
		System.out.println("行动范围3");
		List<Point> roads = find(new Point(4, 4), 3, around);
		Iterator<Point> it =  roads.iterator();
		Point temp = null;
		while(it.hasNext()) {
			temp = it.next();
			road[temp.y][temp.x] = 3;
		}
		road[4][4] = 8;
		//3为行动范围
		print(road);
	}
	
	private static void print(int[][] road) {
		int[] temp = null;
		for(int i=0; i<road.length; i++) {
			temp = road[i];
			//System.out.print("{");
			for(int j=0; j<temp.length; j++) {
				System.out.print(temp[j]);
				if(j<temp.length - 1) {
					System.out.print(" ");
				}
			}
			//System.out.print("},");
			System.out.println();
		}
	}
}
